PATH ∈ NL-complete

定理

$ \mathsf{PATH} \in \textbf{NL-complete}

Proof.

$ \mathsf{PATH} \in \textbf{NL}

$ (v_1, v_2), (v_2, v_3), ... (v_{n-1}, v_n) \in E(G) を判定する関数$ A^{[v_1, v_2, ..., v_n]}(s,t) を次のように定義する

$ A^{[]}(s,t) := 0

$ A^{u :: l}(s,t) := A^l(s, u) \land E_G(u,t)

このとき

$ \braket{G, s, t} \in \textsf{PATH} \iff \exists_{l \in G^{|V(G)|}} A^l(s,t) = 1

計算空間は$ s, tの大きさ, $ |\braket{s,t}| = O\left(\log |V(G)| + \log |V(G)|)\right) = O(\log |V(G)|) = O(\log n)

$ \forall_{L \in \textbf{NL}} \left\lbrack L \le_l \mathsf{PATH} \right\rbrack

$ x \in^? Lの判定のconfiguration graphを$ G_xとする

4. Space complexity#6305d7814507aa00006e8636より$ \|\langle G_x, C_{\tt start}, C_{\tt halt}\rangle\| \le O(|x| \cdot \log|x|)

各状態の空間量が$ O(\log |x|), configurationの数が$ 2^{O(\log|x|)} = O(|x|)